/**
 * 0 onverkend, 1 muur, 2 geen muur
 */

package maze;

import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

public class Maze {
	public static double SECTOR_WIDTH = 40.0;
	ArrayList<Barcode> barcodes;
	private boolean changed = true;// used for gui to indicate if maze has
									// changed and has to be redrawn.

	/**
	 * constructors
	 */
	public Maze(int size) {
		this.size = size;
		data = new char[size + 1][size * 2 + 1];
		barcodes = new ArrayList<Barcode>();
	}

	public Maze(char[][] source) {
		this.size = ((source.length - 1) > ((source[0].length - 1) / 2)) ? (source.length - 1)
				: ((source[0].length - 1) / 2);
		maxx = (source[0].length - 1) / 2 - 1;
		maxy = (source.length - 1) - 1;
		data = new char[this.size + 1][this.size * 2 + 1];
		for (int i = 0; i < source.length; i++) {
			for (int j = 0; j < source[0].length; j++) {
				data[size + 1 - source.length + i][j] = source[i][j];
			}
		}
		barcodes = new ArrayList<Barcode>();
	}

	public Maze(char[][] source, int minx, int maxx, int miny, int maxy) {
		this.size = ((source.length - 1) > ((source[0].length - 1) / 2)) ? (source.length - 1)
				: ((source[0].length - 1) / 2);
		this.minx = minx;
		this.maxx = maxx;
		this.miny = miny;
		this.maxy = maxy;
		data = new char[this.size + 1][this.size * 2 + 1];
		for (int i = 0; i < source.length; i++) {
			for (int j = 0; j < source[0].length; j++) {
				data[size + 1 - source.length + i][j] = source[i][j];
			}
		}
		barcodes = new ArrayList<Barcode>();
	}

	public ArrayList<Barcode> getBarcodes() {
		return barcodes;
	}
	/**
	 * returns the barcode from the string if there is one
	 * 
	 * @param barcode
	 * @return null if there is no barcode with that string
	 */
	public Barcode getBarcodeOnString(String barcode) {
		Barcode bctemp = new Barcode(new Coordinate(0,0),barcode,0);
		for(Barcode bc : barcodes) {
			if(bc.equals(bctemp)) return bc;
		}
		return null;
	}
	
	public void removeBarcode(Coordinate pos){
		//Rare workaround om java.util.ConcurrentModificationException te vermijden.
		//(Je kan geen item uit een lijst verwijderen als je over die lijst aan het itereren bent)
		ArrayList<Barcode> newBarcodes = new ArrayList<Barcode>();
		
		for(Barcode bc: getBarcodes()){
			if(!bc.getPosition().equals(pos)) newBarcodes.add(bc);
		}
		barcodes = newBarcodes;
	}
	
	public void removeBarcode(Barcode bc){
		//Rare workaround om java.util.ConcurrentModificationException te vermijden.
		//(Je kan geen item uit een lijst verwijderen als je over die lijst aan het itereren bent)
		ArrayList<Barcode> newBarcodes = new ArrayList<Barcode>();
		
		for(Barcode currentBC: getBarcodes()){
			if(!currentBC.equals(bc)) newBarcodes.add(bc);
		}
		barcodes = newBarcodes;
	}

	public void addBarcode(Coordinate pos, String BC, int direction) {
		barcodes.add(new Barcode(pos, BC, direction));
	}

	/**
	 * maze implementation
	 */
	// x+ is EAST
	// y+ is NORTH
	// used to bring other Mazes in the same coordinate system
	private Coordinate offset = new Coordinate(0, 0);
	private int size = 32; // 12.8 meter, so the capacity increase probably
							// won't be used
	private char data[][] = new char[size + 1][2 * size + 1];
	private int rot = 0; // how many 90 degree rotations (clockwise) compared to
							// how the map started
	// keep track of max/min to avoid overflows
	private int minx = 0;
	private int miny = 0;
	private int maxx = 0;
	private int maxy = 0;

	private int positivemodulo(int val, int mod) {
		mod = Math.abs(mod); // no negative modulo allowed
		mod = (mod == 0) ? 1 : mod; // no zero modulo either
		while (val < 0)
			val += mod; // increase val until we're sure it's positive
		return val % mod;
	}

	// resizes the matrix if necessary
	private void updateBounds(Coordinate calculated) {
		int tminx = Math.min(minx, calculated.x);
		int tmaxx = Math.max(maxx, calculated.x);
		int tminy = Math.min(miny, calculated.y);
		int tmaxy = Math.max(maxy, calculated.y);
		while ((tmaxx - tminx + 1) > size || (tmaxy - tminy + 1) > size)
			sizeUp();
		if (minx != tminx)
			changed = true;
		if (miny != tminy)
			changed = true;
		if (maxx != tmaxx)
			changed = true;
		if (maxy != tmaxy)
			changed = true;
		minx = tminx;
		maxx = tmaxx;
		miny = tminy;
		maxy = tmaxy;
	}

	// we need to go bigger!
	private void sizeUp() {
		System.out.println("size-up! from " + size + " to " + (2 * size));
		char temp[][] = new char[2 * size + 1][4 * size + 1];
		// top left block
		for (int y = 0; y < -miny; y++) { // min* is 0 or less
			for (int x = 0; x <= ((maxx + 1) * 2); x++) { // max* is 0 or more
				temp[y][x] = data[y][x];
			}
		}
		// bottom left block
		for (int y = size; y >= size - maxy - 1; y--) {
			for (int x = 0; x <= ((maxx + 1) * 2); x++) {
				temp[y + size][x] = data[y][x];
			}
		}
		// top right block
		for (int y = 0; y < -miny; y++) {
			for (int x = size * 2; x > 2 * size + 2 * minx; x--) {
				temp[y][x + 2 * size] = data[y][x];
			}
		}
		// bottom right block
		for (int y = size; y >= size - maxy - 1; y--) {
			for (int x = size * 2; x > 2 * size + 2 * minx; x--) {
				temp[y + size][x + 2 * size] = data[y][x];
			}
		}

		size *= 2;
		data = new char[size + 1][2 * size + 1];
		for (int y = 0; y < size + 1; y++) {
			for (int x = 0; x < 2 * size + 1; x++) {
				data[y][x] = temp[y][x];
			}
		}
	}

	public Coordinate reverseTransform(Coordinate coord) {
		Coordinate newcoord = new Coordinate(0, 0);
		newcoord.x = coord.x;
		newcoord.y = coord.y;
		// reverse offset
		newcoord.x = newcoord.x - offset.x;
		newcoord.y = newcoord.y - offset.y;
		// reverse rotation
		for (int i = 0; i < rot; i++) {
			int temp = newcoord.y;
			newcoord.y = -newcoord.x;
			newcoord.x = temp;
		}
		return newcoord;
	}

	private Coordinate sectorToArray(Coordinate local, Direction wall,
			boolean ownCoordinates) {
		Coordinate matrix = local;
		if (!ownCoordinates) {
			// apply rotation
			for (int i = 0; i < rot; i++) {
				int temp = matrix.x;
				matrix.x = -matrix.y;
				matrix.y = temp;
			}
			switch (rot) {
			case 1:
				wall = wall.left();
				break;
			case 2:
				wall = wall.opposite();
				break;
			case 3:
				wall = wall.right();
				break;
			}
			/*
			 * matrix.x = positivemodulo(matrix.x+offset.x,size); //apply offset
			 * and normalize matrix.y =
			 * positivemodulo(-matrix.y-1-offset.y,size); //apply offset and
			 * normalize while transforming to "y+ is SOUTH"
			 */
			matrix.x = matrix.x + offset.x;
			updateBounds(new Coordinate(matrix.x, matrix.y + offset.y));
			matrix.y = -matrix.y - offset.y -2;

		} else {
			/*
			 * matrix.x = positivemodulo(matrix.x,size); //normalize matrix.y =
			 * positivemodulo(-matrix.y-1,size); //normalize while transforming
			 * to "y+ is SOUTH"
			 */
			updateBounds(matrix);
			matrix.y = -matrix.y - 2;
		}
		// calculate position in matrix
		switch (wall) {
		case NORTH:
			matrix.x = positivemodulo(matrix.x * 2 + 1, size * 2 + 1);
			matrix.y = positivemodulo(matrix.y, size + 1);
			break;
		case SOUTH:
			matrix.x = positivemodulo(matrix.x * 2 + 1, size * 2 + 1);
			matrix.y = positivemodulo(matrix.y + 1, size + 1);
			break;
		case WEST:
			matrix.x = positivemodulo(matrix.x * 2, size * 2 + 1);
			matrix.y = positivemodulo(matrix.y + 1, size + 1);
			break;
		case EAST:
			matrix.x = positivemodulo(matrix.x * 2 + 2, size * 2 + 1);
			matrix.y = positivemodulo(matrix.y + 1, size + 1);
			break;
		}
		return matrix;
	}

	/**
	 * Reads the specified wall from sector (x,y). ownCoordinates: if false,
	 * this function will use the coordinate system that was matched to another
	 * maze otherwise, it will use its own local coordinates
	 */
	public char read(int x, int y, Direction wall, boolean ownCoordinates) {
		Coordinate temp = sectorToArray(new Coordinate(x, y), wall,
				ownCoordinates);
		return data[temp.y][temp.x];
	}

	public void write(int x, int y, Direction wall, char value,
			boolean ownCoordinates) {

		Coordinate temp = sectorToArray(new Coordinate(x, y), wall,
				ownCoordinates);
		data[temp.y][temp.x] = value;
		changed = true;
	}

	/**
	 * matches the coordinate system to another maze where (localx,localy) on
	 * this maze corresponds to (targetx,targety) on the target maze and locald
	 * corresponds to targetd returns false if the points can't be matched, true
	 * on success
	 */
	public boolean match(int localx, int localy, int targetx, int targety,
			Direction locald, Direction targetd) {
		// no rotation change
		if (locald == targetd)
			rot = 0;
		// 1 rotation
		else if (targetd == locald.right()) //target=boven naar onder (south) , local van links naar rechts (east)
			rot = 1;
		// 2
		else if (targetd == locald.opposite())
			rot = 2;
		// 3
		else if (targetd == locald.left())
			rot = 3;
		// the points directions
		else
			return false;
		// apply the rotation
		for (int i = 0; i < rot; i++) {
			int temp = targetx;
			targetx = -targety;
			targety = temp;
		}
		// calculate the differences
		offset.x = localx - targetx;
		offset.y = localy - targety;
		return true;
	}

	public void draw(int posx, int posy) {
		String out = "";
		for (int y = 0; y < (size + 1); y++) {
			for (int x = 0; x < (2 * size + 1); x++) {
				if ((x == 2 * posx + 1) && (y == size - posy + 1)) {
					out += "*";
					continue;
				}
				if (data[y][x] == 1) {
					if (x % 2 != 0)
						out += (((x - 1) / 2) <= maxx) ? "_" : "|";
					else
						out += (((x - 1) / 2) <= maxx) ? "|" : "_";
				} else if (data[y][x] == 0)
					out += "?";
				else
					out += " ";
			}
			out += "\n";
		}
		out += "\n\n";
		System.out.println(out);
	}

	public void draw2(int minx, int maxx, int miny, int maxy,
			boolean ownCoordinates) {
		String out = "";
		for (int x = minx; x <= maxx; x++) {
			out += " ";
			int val = read(x, maxy, Direction.NORTH, ownCoordinates);
			if (val == 1) {
				out += "_";
			} else if (val == 0)
				out += "?";
			else
				out += " ";
		}
		out += "\n";
		for (int y = maxy; y >= miny; y--) {
			int val = read(minx, y, Direction.WEST, ownCoordinates);
			if (val == 1) {
				out += "|";
			} else if (val == 0)
				out += "?";
			else
				out += " ";
			for (int x = minx; x <= maxx; x++) {
				val = read(x, y, Direction.SOUTH, ownCoordinates);
				if (val == 1) {
					out += "_";
				} else if (val == 0)
					out += "?";
				else
					out += " ";
				val = read(x, y, Direction.EAST, ownCoordinates);
				if (val == 1) {
					out += "|";
				} else if (val == 0)
					out += "?";
				else
					out += " ";
			}
			out += "\n";
		}
		out += "\ndone\n";
		System.out.println(out);
	}

	public int getConfirmedXsize() {
		return maxx - minx + 1;
	}

	public int getConfirmedYsize() {
		return maxy - miny + 1;
	}

	public int getMinX() {
		return minx;
	}

	public int getMinXWrap() {
		return positivemodulo(minx, size);
	}

	public int getMaxX() {
		return maxx;
	}

	public int getMinY() {
		return miny;
	}

	public int getMinYWrap() {
		return positivemodulo(miny, size);
	}

	public int getMaxY() {
		return maxy;
	}

	public int getSize() {
		return size;
	}

	public int getRotation() {
		return positivemodulo(rot * -90, 360);
	}

	public List<Direction> getClearDirections(int x, int y) {
		boolean north = read(x,y,Direction.NORTH,true)==2;
		boolean east = read(x,y,Direction.EAST,true)==2;
		boolean south = read(x,y,Direction.SOUTH,true)==2;
		boolean west = read(x,y,Direction.WEST,true)==2;
		List<Direction> possible = new ArrayList<Direction>();
		if (north) {
			possible.add(Direction.NORTH);
		}
		if (east) {
			possible.add(Direction.EAST);
		}
		if (south) {
			possible.add(Direction.SOUTH);
		}
		if (west) {
			possible.add(Direction.WEST);
		}
		return possible;
	}

	public char[][] getRawData() {
		return data.clone();
	}

	public Coordinate getCoordinateOfLocation(Location location) {
		return new Coordinate(
				(int) Math.floor((location.getX() / SECTOR_WIDTH)),
				(int) Math.floor((location.getY() / SECTOR_WIDTH)));
	}

	public Coordinate getCoordinateOfLocation(Location location,
			boolean ownCoordinates) {
		if (ownCoordinates)
			return new Coordinate(
					(int) Math.floor((location.getX() / SECTOR_WIDTH)),
					(int) Math.floor((location.getY() / SECTOR_WIDTH)));
		else {
			Coordinate retval = new Coordinate((int) Math.floor((location
					.getX() / SECTOR_WIDTH)),
					(int) Math.floor((location.getY() / SECTOR_WIDTH)));
			// apply rotation
			for (int i = 0; i < rot; i++) {
				int temp = retval.x;
				retval.x = -retval.y;
				retval.y = temp;
			}
			retval.x = retval.x +offset.x;
			retval.y = retval.y + offset.y;
			return retval;
		}
	}

	public Location getLocationOfCoordinate(Coordinate coordinate) {
		return new Location(coordinate.x * SECTOR_WIDTH + 20, coordinate.y
				* SECTOR_WIDTH + 20);
	}

	public List<Coordinate> getUnexploredCoordinates() {
		List<Coordinate> unexplored = new ArrayList<Coordinate>();
		for (int i = minx; i <= maxx; i++) {
			for (int j = miny; j <= maxy; j++) {
				if (read(i, j, Direction.EAST, true) == 0) {
					if (!unexplored.contains(new Coordinate(i, j))) {
						unexplored.add(new Coordinate(i, j));
					}
					if (i + 1 <= maxx
							&& !unexplored.contains(new Coordinate(i + 1, j))) {
						unexplored.add(new Coordinate(i + 1, j));
					}
				}
				if (read(i, j, Direction.NORTH, true) == 0) {
					if (!unexplored.contains(new Coordinate(i, j))) {
						unexplored.add(new Coordinate(i, j));
					}
					if (j + 1 <= maxy
							&& !unexplored.contains(new Coordinate(i, j + 1))) {
						unexplored.add(new Coordinate(i, j + 1));
					}
				}
			}
		}
		return unexplored;
	}

	public boolean hasThisSectorExplored(Coordinate coordinate) {
		int x = coordinate.getX();
		int y = coordinate.getY();
		if (read(x, y, Direction.EAST, true) == 0)
			return false;
		if (read(x, y, Direction.WEST, true) == 0)
			return false;
		if (read(x, y, Direction.NORTH, true) == 0)
			return false;
		if (read(x, y, Direction.SOUTH, true) == 0)
			return false;
		return true;
	}

	public boolean changed() {
		if (changed) {
			changed = false;
			return true;
		} else
			return false;
	}

	public static void main(String[] args) {
		/*
		 * char mazedata[][] =
		 * {{2,1,2,1,2,1,2},{1,2,2,1,2,2,1},{1,2,1,1,1,2,1},{1,1,2,1,2,1,1}};
		 * Maze m = new Maze(mazedata); m.draw(-1,-1);
		 * System.out.println(((mazedata
		 * .length-1)>((mazedata[0].length-1)/2))?(mazedata
		 * .length-1):((mazedata[0].length-1)/2));
		 * m.write(-2,-2,Direction.NORTH,(char)1,true);
		 * m.write(-2,-2,Direction.EAST,(char)1,true);
		 * m.write(-2,-2,Direction.SOUTH,(char)1,true);
		 * m.write(-2,-2,Direction.WEST,(char)1,true); m.draw(-1,-1);
		 * m.write(-2, 1,Direction.NORTH,(char)1,true); m.write(-2,
		 * 1,Direction.EAST,(char)1,true); m.write(-2,
		 * 1,Direction.SOUTH,(char)1,true); m.write(-2,
		 * 1,Direction.WEST,(char)1,true); m.draw(-1,-1); m.write(
		 * 1,-2,Direction.NORTH,(char)1,true); m.write(
		 * 1,-2,Direction.EAST,(char)1,true); m.write(
		 * 1,-2,Direction.SOUTH,(char)1,true); m.write(
		 * 1,-2,Direction.WEST,(char)1,true); m.draw(-1,-1);
		 * m.write(-4,-4,Direction.NORTH,(char)1,true);
		 * m.write(-4,-4,Direction.EAST,(char)1,true);
		 * m.write(-4,-4,Direction.SOUTH,(char)1,true);
		 * m.write(-4,-4,Direction.WEST,(char)1,true); m.draw(-1,-1);
		 * System.out.println((int)m.read(0,0,Direction.NORTH,true));
		 * System.out.println((int)m.read(0,0,Direction.EAST,true));
		 * System.out.println((int)m.read(0,0,Direction.SOUTH,true));
		 * System.out.println((int)m.read(0,0,Direction.WEST,true));
		 * System.out.println((int)m.read(1,0,Direction.NORTH,true));
		 * System.out.println((int)m.read(1,0,Direction.EAST,true));
		 * System.out.println((int)m.read(1,0,Direction.SOUTH,true));
		 * System.out.println((int)m.read(1,0,Direction.WEST,true));
		 * System.out.println((int)m.read(1,1,Direction.NORTH,true));
		 * System.out.println((int)m.read(1,1,Direction.EAST,true));
		 * System.out.println((int)m.read(1,1,Direction.SOUTH,true));
		 * System.out.println((int)m.read(1,1,Direction.WEST,true));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),0));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),90));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),180));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),270));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),45));
		 * System.out.println(m.getMaxDistance(new Location(30.0,20.0),45));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),225));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),30));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),60));
		 * System.out.println(m.getMaxDistance(new Location(20.0,20.0),120));
		 * System.out.println(m.getMaxDistance(new Location(20.0,260.0),0));
		 * m.write(1,2,Direction.NORTH,(char)0,true); Coordinate[] path =
		 * m.pathToClosestUnknown(0,0,true); for(int i=0;i<path.length;i++) {
		 * System.out.print(path[i].x); System.out.print(",");
		 * System.out.println(path[i].y); } char mazedata0[][] =
		 * {{2,1,2,1,2,1,2},{1,2,2,1,2,2,1},{1,2,1,1,2,2,1},{1,1,2,1,2,1,1}};
		 * Maze m0 = new Maze(mazedata0); System.out.println("Maze 0");
		 * m0.draw2(0,2,0,2,true); char mazedata1[][] =
		 * {{1,2,1,1,2,2,1},{1,1,2,1,2,1,1},{2,1,2,1,2,1,2},{1,2,2,1,2,2,1}};
		 * Maze m1 = new Maze(mazedata1,0,2,-2,0);
		 * System.out.println("Maze 1 (own)"); m1.draw2(0,2,-2,0,true);
		 * m1.match(0, -2, 0, 0, Direction.EAST, Direction.EAST);
		 * System.out.println("Maze 1 (matched)"); m1.draw2(0, 2, 0, 2, false);
		 * char mazedata2[][] =
		 * {{1,1,2,2,1,1,2},{2,1,2,1,1,1,1},{2,1,2,1,2,2,1},{2,1,2,2,1,1,2}};
		 * Maze m2 = new Maze(mazedata2,-1,1,-2,0);
		 * System.out.println("Maze 2 (own)"); m2.draw2(-1,1,-2,0,true);
		 * m2.match(-1, -2, 0, 0, Direction.EAST, Direction.EAST);
		 * System.out.println("Maze 2 (matched)"); m2.draw2(0, 2, 0, 2, false);
		 * char mazedata3[][] =
		 * {{2,1,2,1,2,1,2},{1,2,2,2,2,2,1},{1,2,1,1,1,2,1},{1,1,2,1,2,1,1}};
		 * Maze m3 = new Maze(mazedata3); System.out.println("Maze 3 (own)");
		 * m3.draw2(0,2,0,2,true); m3.match(1, 1, 1, 1, Direction.NORTH,
		 * Direction.EAST); System.out.println("Maze 3 (matched)");
		 * m3.draw2(0,2,0,2, false); m3.match(2, 0, 0, 0, Direction.NORTH,
		 * Direction.EAST); System.out.println("Maze 3 (matched again)");
		 * m3.draw2(0,2,0,2, false);
		 */
		/*char mazedata[][] = { { 2, 1, 2, 1, 2, 1, 2 }, { 1, 2, 2, 1, 2, 2, 1 },
				{ 1, 2, 1, 1, 1, 2, 1 }, { 1, 1, 2, 1, 2, 1, 1 } };
		Maze m = new Maze(mazedata);
		m.sizeUp();
		m.sizeUp();
		m.match(5, 3, 8, 2, Direction.EAST, Direction.EAST);
		m.draw2(-4, 2, 0, 5, false);*/
		Maze m1 = new Maze(5);
		m1.match(1, 1, 1, 0, Direction.NORTH, Direction.WEST);
		System.out.println(m1.reverseTransform(new Coordinate(1,1)));
		System.out.println(m1.reverseTransform(new Coordinate(2,0)));
		System.out.println(m1.reverseTransform(new Coordinate(3,2)));
	}
}

/*
 * 
 * 4x6
 * 
 * ?_?_?_?_? ????| | | ?_?_| | | _ _| | | _| | | | |???? |_ _|????
 * 
 * {{0,1,0,1,0,1,0,1,0}, {0,0,0,0,1,2,1,2,1}, {0,1,0,1,1,2,2,2,1},
 * {1,2,2,1,2,1,1,2,1}, {1,2,2,2,2,1,1,2,1}, {1,2,1,2,1,0,0,0,0},
 * {1,1,2,1,1,0,0,0,0}}
 * 
 * 
 * 
 * 4x4 ?_?_?_?_? | _ _ | |_|_ _ | | _ _ | |_ _ _|_|
 * 
 * {{0,1,0,1,0,1,0,1,0}, {1,2,2,1,2,1,2,2,1}, {1,1,1,1,2,1,2,2,1},
 * {1,2,2,1,2,1,2,2,1}, {1,1,2,1,2,1,1,1,1}}
 */
/*
playNote(PIANO,1661,40);
playNote(PIANO,1661,40);
playNote(PIANO,1661,40);
playNote(PIANO,1661,120);
playNote(PIANO,1319,120);
playNote(PIANO,1480,120);
playNote(PIANO,1661,40);
playNote(PIANO,0,40);
playNote(PIANO,1480,40);
playNote(PIANO,1661,360);
*/